#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef char DataType; //假设结点的数据域类型是字符
typedef struct node { //结点类型定义
    DataType data; //结点的数据域
    struct node *next;//结点的指针域
} ListNode;
typedef ListNode *LinkList;

/**
 * 头插入法(front) 不带头结点
 * 从一个空表开始,重复读入数据,生成新结点,将读入数据存放到新结点的数据域中,然后将新结点插入到当前链表的表头上,直到读入结束标志为止。即每次插入的结点都作为链表的第一个结点。生成的链表中结点的次序和输入的顺序相反
 */
LinkList CreateListF() {
    LinkList head;
    ListNode *p;
    char ch;
    head = NULL; //置空单链表
    ch = getchar(); //读入第一个字符
    while (ch != '\n') //读入字符不是结束标志符时作循环
    {
        p = (ListNode *) malloc(sizeof(ListNode));
        p->data = ch; // 数据域赋值
        p->next = head;//指针域赋值
        head = p; //头指针指向新结点
        ch = getchar(); //读入下一个字符
    }
    return head; //返回链表的头指针
}

/**
 * 尾插入法(rear) 带头结点
 * 该方法是将新结点插入到当前链表的表尾,使其成为当前链表的尾结点。该方法是将新结点插入在当前链表的表尾上,因此需要增设一个尾指针 rear,使其始终指向链表的尾结点。
　　为了简化算法,方便操作,可在链表的开始结点之前附加一个结点,并称其为头结点。
 * @return
 */
LinkList createListR() {
    LinkList head = (ListNode *) malloc(sizeof(ListNode));
    ListNode *p, *rear;
    DataType ch;
    rear = head; //尾指针初始指向头结点
    while ((ch = getchar()) != '\n') {
        p = (ListNode *) malloc(sizeof(ListNode));
        p->data = ch; //数据域赋值
        rear->next = p; //新结点连接到尾结点之后
        rear = p; //尾结点指向新结点
    }
    rear->next = NULL; //终端结点指针域置空
    return head;
}

//带头结点的查找
//按结点序号查找
ListNode *GetNodei(LinkList head, int i) {
    int j;
    ListNode *p;
    p = head->next;
    j = 1; /* 使p指向第一个结点 */
    while (p != NULL && j < i) {
        p = p->next;
        j++;
    } /* 移动指针p , j计数 */
    if (j == i)
        return p;
    else
        return NULL;
}

//按结点值查找
ListNode *LocateNodek(LinkList head, DataType k) {
    //head为带头结点的单链表头指针，k为要查找的结点值
    ListNode *p = head->next;//p指向开始结点
    while (p && p->data != k) {//循环直到p等于NULL 或 p->data等于 k 为止
        p = p->next;//指针指向下一结点
    }
    return p;
}

/**
 * 单链表的插入(带头结点)
 * 插入运算是将值为 e 的新结点插入到表的第 i 个结点的位置上,即插入到 ai-1 与 ai 之间。因此,必须首先找到 ai-1 所在的结点 p,然后生成一个数据域为 e 的新结点 q,q 结点作为 p 的直接后继结点。 head 1    2               3
 *                       p   data next
 */
void InsertList(LinkList head, int i, DataType x) {
    int j = 0;
    ListNode *p, *s;
    p = head;
    while (p != NULL && j < i - 1) {
        p = p->next;
        j++;
    }
    if (p == NULL) {
        printf("ERROR\n ");
        return;
    } else {
        s = (ListNode *) malloc(sizeof(ListNode));
        s->data = x;
        s->next = p->next;
        p->next = s;
    }
}

/**
 * 删除以head为头结点的单链表中的第i个结点
 * @param head
 * @param i
 */
DataType DeleteList(LinkList head, int i) {
    ListNode *p, *s;
    int j = 0, x;
    p = head;

    while (p != NULL && j < i - 1) {//使p指向第 i-1 个结点
        p = p->next;
        j++;
    }
    if (p == NULL) {
        printf("位置错误");
        exit(0);
    } else {
        s = p->next;//s 指向第 i 个结点
        p->next = s->next;//使p->next指向第 i+1 个结点
        x = s->data;//保存被删除的结点值
        free(s);//删除第 i 个结点
        return x;//返回结点值
    }
}

void GetAllNodes(LinkList head, bool isHead) {
    ListNode *p;
    if (isHead == false) {
        putchar(head->data);
    }
    p = head->next;
    while (p != NULL) {
        putchar(p->data);
        p = p->next;
    }
}


int main() {
//    ListNode *node;
    LinkList head;
    head = createListR();
//    GetAllNodes(head, false);
    GetAllNodes(head, true);
//    head = createLinkR();
//    InsertList(head, 3, 'x');
//    GetAllNodes(head, true);
//    node =GetNodei(head, 2);
//    putchar(node->data);
}
